import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 10:01
 * @description 单调栈
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 键为元素，值为下一个更大的元素值
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        int m = nums2.length, n = nums1.length;
        // 从后往前维护单调栈
        for (int i = m - 1; i >= 0; i--) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }
}
